#include <vector>

using namespace std;

// 思路： 双指针，left指向0的下一个位置，right指向2的前一个位置，i为当前遍历位置
// 始终维护[left, i)为1，(right, end]为2， [0, left)为0
class Solution
{
public:
    void sortColors(vector<int> &nums)
    {
        int left = 0;
        int right = nums.size() - 1;
        int i = 0;
        while (i <= right)
        {
            if (nums[i] == 2) // 注意这里不能i++，因为交换过来的元素还没判断
            {
                swap(nums[i], nums[right]);
                --right;
            }
            else if (nums[i] == 0) // 这里可以i++，因为交换过来的元素一定是1
            {
                swap(nums[left], nums[i]);   
                ++i;
                ++left;
            }
            else // nums[i] == 1
            {
                ++i;
            }
        }
    }
};